package demo.practice.leetcode;

public class P222 {
    /*完全二叉树的节点数*/

   /*
   public int countNodes(TreeNode root) {
        if(root==null)
            return 0;
        return countNodes(root.left)+countNodes(root.right)+1;
    }
    */

    //左数高和右边树高相同，则
    public static void main(String[] args) {
        P222 p= new P222();
        p.countNodes(new TreeNode(1));
    }

    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = countLevel(root.left);
        int right = countLevel(root.right);
        if(left == right){
            return countNodes(root.right) + (1<<left);
        }else{
            return countNodes(root.left) + (1<<right);
        }
    }
    private int countLevel(TreeNode root){
        int level = 0;
        while(root != null){
            level++;
            root = root.left;
        }
        return level;
    }
}
